package com.review.dp;

public class a_1 {
    //https://www.bilibili.com/video/BV12W411v7rd
    //青蛙跳石头
    private int dp(int[] arr){
        int[] opt = new int[arr.length];
        opt[0]=arr[0];
        opt[1]=Math.max(arr[0],arr[1]);

        for (int i = 2; i < arr.length; i++) {
            opt[i]=Math.max(opt[i-1],opt[i-2]+arr[i]);
        }
        return opt[arr.length-1];
    }

    public static void main(String[] args) {
        System.out.println(new a_1().dp(new int[]{4,1,1,9,1}));
    }
}
